package com.eddie.search;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

/**
 * 二分查找的前提：该数组是有序的
 * @author Eddie
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] arr = {1, 5, 5, 5, 7, 8, 24};
        List<Integer> integers = binarySearch2(arr, 0, arr.length - 1, 5);
        integers.forEach(System.out::println);
    }

    /**
     * 二分查找算法
     *
     * @param arr     数组
     * @param left    左边的索引
     * @param right   右边的索引
     * @param findVal 要查找的值
     * @return 如果找到就返回下标，没有就返回-1
     */
    public static int binarySearch(int[] arr, int left, int right, int findVal) {
        if (left > right) {
            return -1;
        }
        int mid = (left + right) / 2;
        int minVal = arr[mid];
        //向右递归
        if (findVal > minVal) {
            return binarySearch(arr, mid + 1, right, findVal);
        } else if (findVal < minVal) {
            return binarySearch(arr, left, mid - 1, findVal);
        } else {
            return mid;
        }
    }

    /**
     * 有多个相同值时，返回所有下标
     * <p>
     * 思路分析
     * 1、再找到mid值，不要马上返回
     * 2、先向mid索引值向做扫描，将所有满足查找值的下标加入ArrayList
     * 3、向mid索引值向右边扫描
     * 4、将arrayList返回
     */
    public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {
        if (left > right) {
            return Collections.emptyList();
        }
        int mid = (left + right) / 2;
        int minVal = arr[mid];
        if (findVal > minVal) {//向右递归
            return binarySearch2(arr, mid + 1, right, findVal);
        } else if (findVal < minVal) {
            return binarySearch2(arr, left, mid - 1, findVal);
        } else {
            List<Integer> results = new ArrayList<>();
            int temp = mid - 1;
            while (temp >= 0 && arr[temp] == findVal) {
                results.add(temp);
                temp--;//temp左移
            }
            results.add(mid);//把找到的放进去
            //向mid索引值右边扫描
            temp = mid + 1;
            while (temp <= arr.length - 1 && arr[temp] == findVal) {
                results.add(temp);
                temp++;//temp右移
            }
            return results;
        }
    }
}
